// https://www.acwing.com/problem/content/852/

// 学习这道题包含两方面作用：1. 熟悉邻接表的使用方法；2. 学习优化后版本的 dijkstra 算法

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e6 + 10;
const int INF = 0x3F3F3F3F; // 定义无穷大常量

// 图结构相关变量
int node_count, edge_count; // 节点数和边数

// 邻接表存储图的五个核心数组：
int head[N];                    // 头指针数组，存储每个节点的第一条边的索引
int edge_weight[N];             // 边的权重数组，存储每条边的权重值
int edge_end[N];                // 边的终点数组，存储每条边指向的终点节点
int next_edge[N];               // 下一条边指针数组，存储同一起点的下一条边的索引，形成链表
int edge_index;                 // 边索引计数器，记录当前可用的边索引位置

int shortest_distance[N];       // 存储从起点到各节点的最短距离
bool visited[N];                // 标记节点是否已确定最短距离

/**
 * 向图中添加一条有向边（链式前向星存储图）
 * @param from 边的起点
 * @param to 边的终点
 * @param weight 边的权重
 */
void add_edge(const int from, const int to, const int weight) {
    edge_end[edge_index] = to;              // 将边的终点节点 to 存储到 edge_end 数组中，edge_end数组存储每条边指向的终点节点
    edge_weight[edge_index] = weight;       // 将边的权重 weight 存储到 edge_weight 数组中，edge_weight 数组存储每条边的权重值
    next_edge[edge_index] = head[from];     // 将当前节点的原第一条边设置为新边的下一条边，这相当于在链表头部插入新边，新边指向原来的第一条边
    head[from] = edge_index;                // 更新节点 from 的第一条边为当前新边，这样新边就成为节点a边链表的头节点
    edge_index++;                           // 移动到下一个可用的边索引位
}

/**
 * 使用Dijkstra算法计算从节点1到节点n的最短路径
 * @return 最短路径长度，如果不可达返回-1
 */
int dijkstra() {
    // 初始化所有距离为无穷大
    memset(shortest_distance, 0x3f, sizeof shortest_distance);
    shortest_distance[1] = 0; // 起点到自己的距离为0

    // 使用最小堆优先队列，按距离从小到大排序
    priority_queue<PII, vector<PII>, greater<PII>> min_heap;
    min_heap.push({0, 1}); // 将起点加入队列

    while (!min_heap.empty()) {
        // 取出当前距离最小的节点
        const PII current = min_heap.top();
        min_heap.pop();

        int current_node = current.second;

        // 如果该节点已经处理过，跳过
        if (visited[current_node]) {
            continue;
        }
        visited[current_node] = true;

        // 遍历当前节点的所有邻接边
        for (int edge_ptr = head[current_node]; edge_ptr != -1; edge_ptr = next_edge[edge_ptr]) {
            const int neighbor_node = edge_end[edge_ptr];
            const int edge_weight_value = edge_weight[edge_ptr];

            // 如果找到更短的路径，更新距离并加入队列
            if (shortest_distance[neighbor_node] > shortest_distance[current_node] + edge_weight_value) {
                shortest_distance[neighbor_node] = shortest_distance[current_node] + edge_weight_value;
                min_heap.push({shortest_distance[neighbor_node], neighbor_node});
            }
        }
    }

    // 检查终点是否可达
    if (shortest_distance[node_count] == INF) {
        return -1;
    }
    return shortest_distance[node_count];
}

int main() {
    scanf("%d%d", &node_count, &edge_count);

    // 初始化邻接表头指针
    memset(head, -1, sizeof head);

    // 读取所有边并构建图
    for (int i = 0; i < edge_count; i++) {
        int from, to, weight;
        scanf("%d%d%d", &from, &to, &weight);
        add_edge(from, to, weight);
    }

    // 执行Dijkstra算法并输出结果
    printf("%d\n", dijkstra());

    return 0;
}

/*
5 10
5 3 4
2 4 9
3 4 8
1 3 3
5 3 5
2 5 5
2 1 3
5 4 3
3 4 3
1 3 2

-1
*/